package leetcode;

import java.util.*;

public class LevelOrder2 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        TreeNode right = new TreeNode(20);
        root.right = right;
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        LevelOrder2 levelOrder2 = new LevelOrder2();
        System.out.println(levelOrder2.levelOrder2(root).toString());
        System.out.println(null == null);
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Deque<TreeNode> queue = new ArrayDeque();
//        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> floor = new ArrayList<>();
            List<TreeNode> node_floor = new ArrayList<>();
            while (!queue.isEmpty()) {
                TreeNode temp = queue.remove();
                floor.add(temp.val);
                node_floor.add(temp);
            }
            for (TreeNode treeNode : node_floor) {
                TreeNode left = treeNode.left;
                TreeNode right = treeNode.right;
                if (left != null) {
                    queue.add(left);
                }
                if (right != null) {
                    queue.add(right);
                }
            }
            res.add(floor);
        }
        return res;
    }
}
